/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import com.leetCode.structure.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/13
 */
public class _9_98_ValidateBinarySearchTree {

    List<TreeNode> list = new ArrayList<>();

    public boolean isValidBST2(TreeNode root) {
        return helper(root, null, null);
    }

    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) return true;

        int val = node.val;
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;

        if (! helper(node.right, val, upper)) return false;
        if (! helper(node.left, lower, val)) return false;
        return true;
    }

    public boolean isValidBST(TreeNode root) {
        if (root != null) {
            zx(root);
            int len = list.size();
            for (int i = 1; i < len; i++) {
                if (list.get(i - 1).val >= list.get(i).val) {
                    return false;
                }
            }
        }
        return true;
    }

    private void zx(TreeNode root) {
        if (root.left != null) {
            zx(root.left);
        }
        list.add(root);
        if (root.right != null) {
            zx(root.right);
        }
    }

    /*private boolean zx(TreeNode root, TreeNode parent) {
        if (root == null) {
            return true;
        }
        zx(root.left, root);
        if (parent != null && parent.val >= root.val) {
            return false;
        }
        return zx(root.right, root);
    }*/

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(3);
        root.left = t1;
        root.right = t2;
        /*TreeNode root = new TreeNode(5);
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(4);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(6);
        root.left = t1;
        root.right = t2;
        t2.left = t3;
        t2.right = t4;*/
        /*TreeNode root = new TreeNode(1);
        TreeNode t1 = new TreeNode(1);
        root.left = t1;*/
        System.out.println(new _9_98_ValidateBinarySearchTree().isValidBST2(root));
    }
}
